<!DOCTYPE html>
<html lang="zh">

<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>
    
    排序 - DSRBLOG
    
  </title>
  

  
  
  <link href="atom.xml" rel="alternate" title="DSRBLOG" type="application/atom+xml">
  <link rel="stylesheet" href="asset/css/style.min.css">
  <link rel="stylesheet" href="asset/css/doc.css">
  <script src="asset/app.js"></script>


</head>

<body> <section class="ct-body">
	<div class="container">
		<div class="columns is-variable bd-klmn-columns is-4 is-centered">
			<div class="column is-four-fifths">
				<div class="post-body single-content">
					
					<h1 class="title">
						排序
					</h1>


					<div class="media">
						
						
						<div class="media-content">
							<div class="content">
								<p>
									<span class="date">2022/03/21 03:20 上午</span>
									

									

									<br />
									<span class="tran-tags">Tags:</span>&nbsp;
									
									<a class="tag is-link is-light">#数据结构与算法</a>
									

								</p>
							</div>
						</div>

					</div>
				</div>
				<article class="markdown-body single-content">
					<h2><a id="%E6%A6%82%E8%BF%B0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>概述</h2>
<ul>
<li>排序概念：将一组杂乱无章的数据按一定的规律顺次排列起来</li>
<li>排序目的：便于查找</li>
</ul>
<h3><a id="%E8%A1%A1%E9%87%8F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%9A%84%E4%BC%98%E5%8A%A3" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>衡量排序算法的优劣</h3>
<ul>
<li>时间效率：排序速度（即排序所花费的全部比较次数）</li>
<li>空间效率：占内存辅助空间的大小</li>
<li>稳定性：若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的，否则称为不稳定的排序算法</li>
</ul>
<h3><a id="%E5%86%85%E9%83%A8%E6%8E%92%E5%BA%8F%E5%92%8C%E5%A4%96%E9%83%A8%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>内部排序和外部排序</h3>
<ul>
<li>若待排序记录都在内存中，称为内部排序</li>
<li>若待排序记录一部分在内存，一部分在外存，则成为外部排序</li>
</ul>
<h4><a id="%E5%86%85%E9%83%A8%E6%8E%92%E5%BA%8F%E7%9A%84%E7%AE%97%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>内部排序的算法</h4>
<p>按<strong>排序规则</strong>可分5类：</p>
<ul>
<li>插入排序</li>
<li>交换排序（重点是快速排序）</li>
<li>选择排序</li>
<li>归并排序</li>
<li>基数排序</li>
</ul>
<p>按<strong>排序算法的时间复杂度</strong>可分3类：</p>
<ul>
<li>简单的排序算法：时间效率低，O(n<sup>2</sup>)</li>
<li>先进的排序算法：时间效率高，O(n · log<sub>2</sub>n)</li>
<li>基数排序算法：时间效率高，O(d * n)</li>
</ul>
<h3><a id="%E5%BE%85%E6%8E%92%E5%BA%8F%E8%AE%B0%E5%BD%95%E5%9C%A8%E5%86%85%E5%AD%98%E4%B8%AD%E7%9A%84%E5%AD%98%E5%82%A8%E5%92%8C%E5%A4%84%E7%90%86" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>待排序记录在内存中的存储和处理</h3>
<ul>
<li>顺序排序：排序时直接移动记录</li>
<li>链表排序：排序时只移动指针</li>
<li>地址排序：排序时先移动地址，再移动记录</li>
</ul>
<h4><a id="%E9%A1%BA%E5%BA%8F%E7%BB%93%E6%9E%84%EF%BC%88%E9%A1%BA%E5%BA%8F%E8%A1%A8%EF%BC%89%E7%9A%84%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序结构（顺序表）的抽象数据类型</h4>
<pre class="line-numbers"><code class="language-c">#define MAXSIZE 20   //设记录不超过20个
typedef int KeyType; //设关键字为整型
typedef struct
{
    KeyType key;        //关键字
    InfoType otherinfo; //其它数据项
} RecordType;

typedef struct
{
    RecordType r[MAXSIZE + 1]; //存储顺序表的向量，r[0]一般作哨兵或缓冲区
    int length;                //顺序表的长度
} SqList;
</code></pre>
<h2><a id="%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>插入排序</h2>
<p>每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到全部对象插入完毕</p>
<h3><a id="%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>直接插入排序</h3>
<p>在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移</p>
<h4><a id="%E5%AE%9E%E7%8E%B0%E6%AD%A5%E9%AA%A4%EF%BC%9A" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>实现步骤：</h4>
<ul>
<li>比较</li>
<li>移动</li>
</ul>
<pre class="line-numbers"><code class="language-c">void InsertSort(SqList &amp;L)
{
    int i, j;
    for (i = 2; i &lt;= L.length; i++)
    {
        //判断当前元素是否小于上一个元素
        if (L.r[i].key &lt; L.r[i - 1].key)
        {
            //将当前元素存入缓冲区
            L.r[0] = L.r[i];
            //从当前元素的上一个元素开始从后向前进行比较
            for (j = i - 1; L.r[0].key &lt; L.r[j].key; j--)
                //使用当前元素覆盖后一个元素,直至当前比较的元素小于r[0]
                L.r[j + 1] = L.r[j];
            //用r[0]覆盖当前元素的后一位
            L.r[j + 1] = L.r[0];
        }
    }
}
</code></pre>
<h4><a id="%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>算法分析</h4>
<p>若待排序的对象有n个，则算法需要进行n - 1次插入</p>
<ul>
<li>
<p><strong>最好情况：</strong> 排序前对象已经按关键码大小从小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键码比较依次，对象不需要移动，因此总的关键码比较次数为n - 1</p>
</li>
<li>
<p><strong>最坏情况：</strong> 第i次插入时，第i个对象必须与前面i - 1个元素都做关键码比较，并且每做1次比较就要移动1次数据，则总的关键码比较次数KCN和对象移动次数RMN分别为：</p>
</li>
</ul>
<p><img src="media/16478040168232/16478802353510.jpg" alt="" /></p>
<ul>
<li>若待排序对象中出现各种排序的概率相同，则可取上述最好情况和最坏情况的<strong>平均情况</strong>，在平均情况下的关键码比较次数和对象移动次数约为<strong>n<sup>2</sup> / 4</strong>，因此，直接插入排序的时间复杂度为<strong>O(n<sup>2</sup>)</strong></li>
<li>空间效率：<strong>O(1)</strong>（<strong>仅占用一个缓冲单元</strong>）</li>
<li>直接插入排序是一种稳定的排序方法</li>
</ul>
<h3><a id="%E6%8A%98%E5%8D%8A%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>折半插入排序</h3>
<p>在已形成的有序表中折半查找，并在适当位置插入，把原来位置上的元素向后顺移</p>
<ul>
<li>优点：比较的次数大大减少</li>
</ul>
<h4><a id="%E5%AE%9E%E7%8E%B0%E6%AD%A5%E9%AA%A4%EF%BC%9A" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>实现步骤：</h4>
<pre class="line-numbers"><code class="language-c">void BInsertSort(SqList &amp;L)
{
    int i, j;
    int low, high, mid;
    for (i = 2; i &lt;= L.length; i++)
    {
        //将当前元素存入缓冲区
        L.r[0] = L.r[i];
        low = 1;
        //折半查找的上界为当前元素之前的所有元素
        high = i - 1;
        //当折半查找的下界大于等于上界时，循环结束，找到r[0]应该插入的位置
        while (low &lt;= high)
        {
            //定位到当前查找范围的正中奖
            mid = (low + high) / 2;
            //将当前元素与r[0]进行比较，并缩小范围
            if (L.r[0].key &lt; L.r[mid].key)
                high = mid - 1;
            else
                low = mid + 1;
        }
        //从当前元素的前一个元素开始从后往前移动元素
        for (j = i - 1; j &gt;= high + 1; j--)
            L.r[j + 1] = L.r[j];
        L.r[high + 1] = L.r[0];
    }
}
</code></pre>
<h4><a id="%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>算法分析</h4>
<p>折半查找比顺序查找快，所以折半查找排序就平均性能来说比直接插入排序要快</p>
<ul>
<li>在插入第i个对象时，需要经过<strong>log<sub>2</sub>i + 1</strong>次关键码比较，才能确定它应该插入的位置</li>
<li>时间效率：虽然比较次数大大减少，但<strong>移动次数并未减少</strong>，所以时间效率仍为<strong>O(n<sup>2</sup>)</strong></li>
<li>空间效率：<strong>O(1)</strong></li>
<li>折半插入排序是一种稳定的排序方法</li>
</ul>
<h3><a id="%E5%B8%8C%E5%B0%94%EF%BC%88shell%EF%BC%89%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>希尔（shell）排序</h3>
<p>又称缩小增量排序，先将整个待排序列表<strong>分割成若干子序列</strong>，分别进行直接插入排序，待整个列表中的记录“基本有序”时，再对全体记录进行一次直接插入排序</p>
<p><img src="media/16478040168232/16478822413449.jpg" alt="" /></p>
<ul>
<li>
<p>技巧：子序列的构成并不是简单地“逐段分割”，而是将相隔某个<strong>增量dk</strong>的记录组成一个子序列，让<strong>增量dk逐趟缩短</strong>（例如依次取5、3、1），直到<strong>dk = 1</strong></p>
</li>
<li>
<p>优点：让关键字值小的元素能够快速前移，且序列基本有序时，再用直接插入排序处理，时间效率会高很多</p>
</li>
</ul>
<h4><a id="%E5%AE%9E%E7%8E%B0%E6%AD%A5%E9%AA%A4" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>实现步骤</h4>
<pre class="line-numbers"><code class="language-c">void ShellInsert(SqList &amp;L, int dk)
{
    int i, j;
    //从第dk+1位开始比较
    for (i = dk + 1; i &lt;= L.length; i++)
    {
        //将当前元素与dk位之前的元素进行比较
        if (L.r[i].key &lt; L.r[i - dk].key)
        {
            //将当前元素存入缓冲区
            L.r[0] = L.r[i];
            //使当前元素覆盖dk位之前的元素
            for (j = i - dk; j &gt; 0 &amp;&amp; L.r[0].key &lt; L.r[j].key; j -= dk)
                L.r[j + dk] = L.r[j];
            //使缓冲区的元素覆盖当前元素
            L.r[j + dk] = L.r[0];
        }
    }
}

void ShellSort(SqList &amp;L, int dlta[], int t)
{
    int k;
    for (k = 0; k &lt; t; k++)
        // dlta[]是用户定义的数组值，存储增量dk
        ShellInsert(L, dlta[k]);
}
</code></pre>
<h4><a id="%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>算法分析</h4>
<ul>
<li>时间效率：<strong>O(n<sup>1.25</sup>)</strong> ~ <strong>O(1.6n<sup>1.25</sup>)</strong>（经验公式）</li>
<li>空间效率：<strong>O(1)</strong>（仅占用1个缓冲单元）</li>
<li>算法的稳定性：不稳定</li>
</ul>
<h2><a id="%E4%BA%A4%E6%8D%A2%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>交换排序</h2>
<p>交换排序就是两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序</p>
<h3><a id="%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>冒泡排序</h3>
<p>每趟排序不断比较相邻元素，并按“前小后大”或“前大后小”规则交换位置</p>
<ul>
<li>优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其它元素，一旦下一趟没有交换发生，还可以提前结束排序</li>
<li>前提：顺序存储结构</li>
</ul>
<h4><a id="%E5%AE%9E%E7%8E%B0%E6%AD%A5%E9%AA%A4" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>实现步骤</h4>
<pre class="line-numbers"><code class="language-c">void BubbleSort(SqList &amp;L)
{
    int i, j;
    int k = 1;
    RedType t;
    for (i = 1; i &lt; L.length &amp;&amp; k == 1; i++)
    {
        k = 0;
        for (j = 1; j &lt; L.length - i; j++)
        {
            //判断当前元素是否大于下一个元素
            if (L.r[j].key &gt; L.r[j + 1].key)
            {
                k = 1;
                //交换当前元素与下一个元素的位置
                t = L.r[j];
                L.r[j] = L.r[j + 1];
                L.r[j + 1] = t;
            }
        }
    }
}
</code></pre>
<h4><a id="%E6%80%A7%E8%83%BD%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>性能分析</h4>
<ul>
<li>最好情况：初始排列已有序，只执行一趟起泡，做<code>n - 1</code>次关键码比较，不移动对象</li>
<li>最坏情况：初始排列逆序，算法执行<code>n - 1</code>趟起泡，第i趟（i &lt; n）做了<code>n - i</code>次关键码比较，执行了<code>n - i</code>次对象交换，此时比较总次数KCN和记录移动次数RMN为：<br />
<img src="media/16478040168232/16478857480318.jpg" alt="" /></li>
<li>时间效率：<strong>O(n<sup>2</sup>)</strong></li>
<li>空间效率：<strong>O(1)</strong></li>
<li>稳定性：稳定</li>
</ul>
<h3><a id="%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>快速排序</h3>
<p>从待排序列中<strong>任取一个元素（例如取第一个）作为中心</strong>，所有<strong>比它小的元素一律前放</strong>，所有<strong>比它大的元素一律后放</strong>，形成左右两个子表，然后再<strong>对各子表重新选择中心元素并依此规则调整</strong>，直到每个子表的元素只剩一个，此时便为有序序列</p>
<ul>
<li>优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快</li>
<li>前提：顺序存储结构</li>
</ul>
<p><img src="media/16478040168232/16478870552501.jpg" alt="" /></p>
<p>在第一趟排序完成后，对各子表递归排序过程</p>
<p><img src="media/16478040168232/16478872480459.jpg" alt="" /></p>
<h4><a id="%E5%AE%9E%E7%8E%B0%E6%AD%A5%E9%AA%A4" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>实现步骤</h4>
<ul>
<li>每一趟子表的形成从两头向中间交替式逼近</li>
<li>由于每趟中对各子表的操作相似，可以采用递归算法</li>
</ul>
<pre class="line-numbers"><code class="language-c">//排序算法
int Partition(SqList &amp;L, int low, int high)
{
    KeyType pivotkey;
    L.r[0] = L.r[low];
    pivotkey = L.r[low].key;
    while (low &lt; high)
    {
        //移动high，直到r[high]所在的元素小于r[0]
        while (low &lt; high &amp;&amp; L.r[high].key &gt;= pivotkey)
            high--;
        L.r[low] = L.r[high];
        //移动low，直到r[low]所在的元素大于r[0]
        while (low &lt; high &amp;&amp; L.r[low].key &lt;= pivotkey)
            low++;
        L.r[high] = L.r[low];
    }
    L.r[low] = L.r[0];
    return low;
}
//递归算法
void QSort(SqList &amp;L, int low, int high)
{
    int pivotloc;
    if (low &lt; high)
    {
        pivotloc = Partition(L, low, high);
        //出轴位左侧子表排序
        QSort(L, low, pivotloc - 1);
        //出轴位右侧子表排序
        QSort(L, pivotloc + 1, high);
    }
}

void QuickSort(SqList &amp;L)
{
    QSort(L, 1, L.length);
}
</code></pre>
<h4><a id="%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>算法分析</h4>
<p>可以证明，函数QuickSort的平均计算时间是<strong>O(n · log<sub>2</sub>n)</strong>，实验结果表明，就<strong>平均计算时间</strong>而言，快速排序是我们所讨论的所有<strong>内排序方法中最好的一个</strong></p>
<p>快速排序是<strong>递归</strong>的，需要有一个栈存放每层递归调用时的指针和参数（新的low和high），<strong>最大递归调用层次数与递归树的深度一致</strong>，理想情况为<strong>log<sub>2</sub>(n + 1)</strong>，因此，要求存储开销为<strong>O(log<sub>2</sub>n)</strong></p>
<ul>
<li>最好情况：如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况，此时，快速排序的趟数最少</li>
<li>最坏情况：即待排序对象<strong>已经按其关键码从小到大排好序的情况下</strong>，其递归树称为<strong>单支树</strong>，每次划分只得到<strong>比上一次少一个对象的子序列</strong>，这样，必须经过<strong>n - 1</strong>趟才能把所有对象定位，并且第i趟需要经过<strong>n - i</strong>次关键码比较才能找到第i个对象的安放位置，总的关键码比较次数将达到<strong>n<sup>2</sup> / 2</strong></li>
<li>稳定性：不稳定</li>
<li>平均排序效率为<strong>O(n · log<sub>2</sub>n)</strong>，但最坏情况（例如已经有序）仍为<strong>O(n<sup>2</sup>)</strong></li>
</ul>
<h2><a id="%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>选择排序</h2>
<p>每一趟在后面n - 1个待排序记录中选取关键字最小的记录作为有序序列中的第i个记录</p>
<h3><a id="%E7%AE%80%E5%8D%95%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>简单选择排序</h3>
<p>每经过一趟比较就找出一个最小值，与待排序序列最前面的位置互换即可</p>
<ul>
<li>优点：实现简单</li>
<li>缺点：每趟只能确定一个元素，表长为n时需要n - 1趟</li>
<li>前提：顺序存储结构</li>
</ul>
<p><img src="media/16478040168232/16479381934642.jpg" alt="" /></p>
<h4><a id="%E5%AE%9E%E7%8E%B0%E6%AD%A5%E9%AA%A4" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>实现步骤</h4>
<p>在n个记录中选择最小值放到r[1]位置，然后从剩余的n - 1个记录中选择最小值放到r[2]位置，如此反复，直到全部有序</p>
<pre class="line-numbers"><code class="language-c">void SelectSort(SqList &amp;L)
{
    int i, j, k;
    RedType t;
    for (i = 1; i &lt; L.length; i++)
    {
        //初始化记录当前元素的下标
        k = i;
        for (j = i + 1; j &lt; L.length; j++)
            //如果比较的元素更小，记录当前比较元素的下标
            if (L.r[j].key &lt; L.r[k].key)
                k = j;
        //如果当前记录的下标和当前元素不一致，交换位置
        if (i != k)
        {
            t = L.r[i];
            L.r[i] = L.r[k];
            L.r[k] = t;
        }
    }
}
</code></pre>
<h4><a id="%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>算法分析</h4>
<ul>
<li>时间效率：<strong>O(n<sup>2</sup>)</strong>（虽然移动次数较少，但比较次数较多）</li>
<li>空间效率：<strong>O(1)</strong>（交换时只用一个缓存单元）</li>
<li>稳定性：不稳定</li>
</ul>
<h3><a id="%E9%94%A6%E6%A0%87%E8%B5%9B%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>锦标赛排序</h3>
<h3><a id="%E5%A0%86%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>堆排序</h3>
<p>堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的<strong>最坏、最好、平均时间复杂度均为O(n · log n)</strong>，它也是不稳定排序</p>
<p>基本思想：</p>
<ul>
<li>将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列</li>
</ul>
<h4><a id="%E5%A0%86" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>堆</h4>
<p>堆是具有以下性质的完全二叉树：</p>
<ul>
<li>每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆</li>
<li>每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆</li>
</ul>
<p><img src="media/16478040168232/16482239482668.jpg" alt="" /></p>
<h2><a id="%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>归并排序</h2>
<p>基本思想：</p>
<ul>
<li>将两个（或以上）的有序表组成新的有序表</li>
</ul>
<p>实际意义：</p>
<ul>
<li>可以把<strong>一个长度为n的无序序列</strong>看成是<strong>n个长度为1的有序子序列</strong>，两两归并，得到<strong>n / 2个长度为2的子序列</strong>，再两两归并，如此反复，直到最后得到一个长度为n的有序序列</li>
</ul>
<p><img src="media/16478040168232/16479391729923.jpg" alt="" /></p>
<h4><a id="%E5%AE%9E%E7%8E%B0%E6%AD%A5%E9%AA%A4" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>实现步骤</h4>
<pre class="line-numbers"><code class="language-c">void Merge(RedType SR[], RedType TR[], int i, int m, int n)
{
    // m为SR[]最中间的元素的下标
    int j, k;
    // j初始化为SR[]后半段第一个元素的下标，i初始化为SR[]前半段第一个元素的下标
    for (j = m + 1, k = i; i &lt;= m &amp;&amp; j &lt;= n; k++)
    {
        //比较下标为i和j的元素，将较小的元素填入TR[]中
        if (SR[i].key &lt; SR[j].key)
        {
            TR[k] = SR[i];
            i++;
        }
        else
        {
            TR[k] = SR[j];
            j++;
        }
    }
    while (i &lt;= m)
    {
        TR[k] = SR[i];
        k++;
        i++;
    }
    while (j &lt;= n)
    {
        TR[k] = SR[j];
        k++;
        j++;
    }
}

void MSort(RedType SR[], RedType TR1[], int s, int t)
{
    int m;
    RedType TR2[MAXSIZE + 1];
    if (s == t)
        TR1[s] = SR[s];
    else
    {
        //将SR[]拆分为两段，对前半段和后半段分别进行递归
        m = (s + t) / 2;
        MSort(SR, TR2, s, m);
        MSort(SR, TR2, m + 1, t);
        //将前半段与后半段
        Merge(TR2, TR1, s, m, t);
    }
}

void MergeSort(SqList &amp;L)
{
    MSort(L.r, L.r, 1, L.length);
}
</code></pre>
<h4><a id="%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>算法分析</h4>
<ul>
<li>
<p>一趟归并的操作是：调用<strong>n / 2h</strong>次算法<strong>merge</strong>将<strong>SR[1...n]中前后相邻且长度为h的有序段</strong>进行两两归并，得到<strong>前后长度为2h的有序段</strong>，并存放在TR[1...n]中，整个归并排序需要进行<strong>log<sub>2</sub>n</strong>趟，所以算法总的时间复杂度为<strong>O(n·log<sub>2</sub>n)</strong></p>
</li>
<li>
<p>因为需要一个与原始序列同样大小的辅助序列（TR），所以空间效率为<strong>O(n)</strong></p>
</li>
<li>
<p>稳定性：稳定（是先进排序中为数不多的稳定算法 ）</p>
</li>
</ul>

				</article>
				<div class="comments-wrap">
					<div class="share-comments">
						

						

						
					</div>
				</div><!-- end comments wrap -->
			</div>
		</div><!-- end columns -->
	</div><!-- end container -->
</section>  














<script src="asset/prism.js"></script>









</body>

</html>